/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        222.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/17 9:59
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
//
//完全二叉树 的定义如下：在完全二叉树中，
// 除了最底层节点可能没填满外，其余每层节点数都达到最大值，
// 并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2h个节点
#include "../header.h"
#include <cmath>

class Solution {
public:
    int countNodes(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }
        TreeNode *left = root->left, *right = root->right;
        int lh = 0, rh = 0;
        while (left != nullptr) {
            lh++;
            left = left->left;
        }
        while (right != nullptr) {
            rh++;
            right = right->right;
        }
        if (lh == rh) {
            return (1 << (lh + 1)) - 1;
        }
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
